package com.exam.practice;

import java.util.Arrays;

/**
 * @Author: xin.wang  E-mail:xin.wang1@myt11.com
 * @CreateTime: 2022/1/13 13:56
 * @Description: 合并两个有序的数组
 */
public class SecondPractice {
    /**
     * 给出一个有序的整数数组A和有序的整数数组B，请将数组B合并到数组A中，变成一个有序的升序数组
     * 注意：
     * 1.保证 A 数组有足够的空间存放 B 数组的元素， A 和 B 中初始的元素数目分别为 m 和 n，A的数组空间大小为 m+n
     * 2.不要返回合并的数组，将数组 B 的数据合并到 A 里面就好了
     * 3.A 数组在[0,m-1]的范围也是有序的
     *
     * 示例
     * 输入：[4,5,6],[1,2,3]
     * 返回值：[1,2,3,4,5,6]
     * 说明：A数组为[4,5,6]，B数组为[1,2,3]，后台程序会预先将A扩容为[4,5,6,0,0,0]，B还是为[1,2,3]，m=3，n=3，传入到函数merge里面，
     *      然后请完成merge函数，将B的数据合并A里面，最后后台程序输出A数组
     * @param args
     */
    public static void main(String[] args) {
        int[] arraysA = {1,2,3,0,0,0};
        int[] arraysB = {-2,5,6};
        SecondPractice secondPractice = new SecondPractice();
        secondPractice.merge(arraysA,3,arraysB,3);
        System.out.println(Arrays.toString(arraysA));
    }

    /**
     * 插入排序
     * @param arraysA
     * @param m
     * @param arraysB
     * @param n
     */
    public void merge(int[] arraysA , int m , int[] arraysB , int n){
        for (int i = m; i<m+n ;i++) {
            arraysA[i] = arraysB[i - m];
        }
        int oIndex = 0;
        while (oIndex < n) {
            int iIndex = m - 1 + oIndex;
            //遍历数组B的每个元素,获取数组A的每个位置然后插入进去
            while (iIndex>=0 && arraysA[iIndex] > arraysB[oIndex]){
                arraysA[iIndex+1] = arraysA[iIndex];
                iIndex--;
            }
            arraysA[iIndex+1] = arraysB[oIndex];
            oIndex++;
        }
    }

//    public void merge(int[] arraysA , int m , int[] arraysB , int n){
//        int i = m-1;
//        int j = n-1;
//        int index = m+n-1; //数组合并后的角标
//        while (j >= 0) {
//            if (i >= 0) {
//                if (arraysA[i]>arraysB[i]){
//                    arraysA[index] = arraysA[i];
//                    i--;
//                }else {
//                    arraysA[index] = arraysB[j];
//                    j--;
//                }
//            }else {
//                arraysA[index] = arraysB[j];
//                j--;
//            }
//            index--;
//        }
//        //数组B为0和俩数组都为0,不用合并
//        if (n == 0 && (m == 0 && n == 0)) {
//            return;
//        }
//        //数组A为0,B不为0,将B合并到A
//        else if (m == 0 && n != 0) {
//            for (int i =0;i<n;i++){
//                arraysA[i] = arraysB[i];
//            }
//            return;
//        }
//    }

}
